package dynamic;

import java.util.Arrays;

import org.junit.Test;

import utils.ArrayGenerator;

public class Ex494 {
    class Solution1 {
        public int findTargetSumWays(int[] nums, int target) {
            if (nums.length == 0) return target == 0 ? 1 : 0;
            return dfs(nums, 0, 0, target);
        }

        public int dfs(int[] nums, int idx, int cur, int target/* , boolean add */) {
            if (idx == nums.length) {
                return cur == target ? 1 : 0;
            }
            int add = dfs(nums, idx + 1, cur + nums[idx], target);
            int sub = dfs(nums, idx + 1, cur - nums[idx], target);
            return add + sub;
        }
    }

    class Solution {

        /* 
            1. 变化量： idx, cur
            2. 变化范围: 0 ~ len; -sum ~ sum
            3. 状态定义：f[i][j] 表示：已经遍历到下标为i，且累计和为j的情况下，能得到target的方案数
            4. 找到递归表达式：dfs(nums, idx + 1, cur + nums[idx], target) + dfs(nums, idx + 1, cur - nums[idx], target);
                f[i][j] = f[i + 1][j - nums[i]] + f[i + 1][j + nums[i]]
            5. 最终返回状态：我想直到从(0, sum) 到达(len, target)的方案数, 因此最终状态为(0, sum)
            6. 初始定义：当idx到达len时，能不能得到target已经确定了，那就是只有f[len][target] == 1, 剩下全部为0
        */
        public int findTargetSumWays1(int[] nums, int target) {
            int len;
            if ((len = nums.length) == 0) return target == 0 ? 1 : 0;
            int sum = 0;
            for (int i = 0; i < len; i++) sum += nums[i];
            int[][] f = new int[len + 1][2 * sum + 1]; //变化范围： 0 ~ len; -sum ~ sum[共2*sum + 1个数]
            f[len][target + sum] = 1; //最后一层只有一个值为1，剩下默认0
            for (int i = len - 1; i >= 0; i--) {
                for (int j = 0; j <= 2 * sum; j++) {
                    f[i][j] = 0;
                    if (j - nums[i] >= 0) f[i][j] += f[i + 1][j - nums[i]];
                    if (j + nums[i] <= 2 * sum) f[i][j] += f[i + 1][j + nums[i]];
                }
            }
            return f[0][sum];
        }

        /* 
            又是老掉牙的空间优化环节。。。
            f[i][j]只与下一层的表格有关，因此可以使用一维数组
        */
        public int findTargetSumWays(int[] nums, int target) {
            int len;
            if ((len = nums.length) == 0) return target == 0 ? 1 : 0;
            int sum = 0;
            for (int i = 0; i < len; i++) sum += nums[i];
            int[] f = new int[2 * sum + 1]; //变化范围： 0 ~ len; -sum ~ sum[共2*sum + 1个数]
            f[target + sum] = 1; //最后一层只有一个值为1，剩下默认0
            for (int i = len - 1; i >= 0; i--) {
                // for (int j = sum; j >= 0; j--) {
                for (int j = 0; j <= 2 * sum; j++) {
                    f[j] = 0;
                    if (j - nums[i] >= 0) f[j] += f[j - nums[i]];
                    if (j + nums[i] <= 2 * sum) f[j] += f[j + nums[i]];
                }
            }
            return f[sum];
        }

    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = {1, 1, 1, 1, 1};
        // nums = ArrayGenerator.getArray(20, 20);
        // System.out.println(Arrays.toString(nums));
        System.out.println(s.findTargetSumWays(nums, 3));
    }
}
